import java.util.ArrayList;
import java.util.List;

/**
 * 面试题17：打印从 1 到最大的 n 位数
 */
public class Offer_17 {
    /**
     * 本题考点：大数
     */
    /**
     * 方法二：递归全排列
     * <p>
     * n 位所有十进制数就是 n 个从 0 到 9 的全排列
     */
    public void printNumbers(int n) {
        if (n <= 0) {
            return;
        }
        StringBuilder number = new StringBuilder(n);
        for (int i = 0; i < n; i++) {
            number.append('0');
        }
        for (int i = 0; i < 10; i++) {
            number.setCharAt(0, (char) (i + '0'));
            recur(number, 0);
        }
    }

    private void recur(StringBuilder number, int index) {
        int len = number.length();
        if (index == len - 1) {
            print(number);
            return;
        }
        for (int i = 0; i < 10; i++) {
            number.setCharAt(index + 1, (char) (i + '0'));
            recur(number, index + 1);
        }
    }

    // **********************************

    /**
     * 方法一：字符串模拟
     */
    public void printNumbers2(int n) {
        if (n <= 0) {
            return;
        }

        // 1. 用 List<Character> 模拟
        // List<Character> number = new ArrayList<>(n);
        // for (int i = 0; i < n; i++) {
        // number.add('0');
        // }

        // 2. 用 StringBuilder 模拟
        StringBuilder number = new StringBuilder(n);
        for (int i = 0; i < n; i++) {
            number.append('0');
        }

        while (!increment(number)) {
            print(number);
        }
    }

    /**
     * 实现在表示数字的字符串 number 上加 1
     */
    private boolean increment(StringBuilder number) {
        boolean isOverflow = false;
        int nTakeover = 0;
        int len = number.length();
        for (int i = len - 1; i >= 0; i--) {
            int nSum = number.charAt(i) - '0' + nTakeover;
            if (i == len - 1) {
                nSum++;
            }
            if (nSum >= 10) {
                if (i == 0) {
                    isOverflow = true;
                } else {
                    nSum -= 10;
                    nTakeover = 1;
                    number.setCharAt(i, (char) ('0' + nSum));
                }
            } else {
                number.setCharAt(i, (char) ('0' + nSum));
                break;
            }
        }
        return isOverflow;
    }

    /**
     * 打印 number
     */
    private void print(StringBuilder number) {
        boolean isBegin0 = true;
        int len = number.length();
        for (int i = 0; i < len; i++) {
            // 碰到第一个非 '0' 字符才开始打印
            if (isBegin0 && number.charAt(i) != '0') {
                isBegin0 = false;
            }
            if (!isBegin0) {
                System.out.print(number.charAt(i));
            }
        }
        System.out.println();
    }

    private boolean increment(List<Character> number) {
        boolean isOverflow = false;
        int nTakeover = 0;
        int len = number.size();
        for (int i = len - 1; i >= 0; i--) {
            int nSum = number.get(i) - '0' + nTakeover;
            if (i == len - 1) {
                nSum++;
            }
            if (nSum >= 10) {
                if (i == 0) {
                    isOverflow = true;
                } else {
                    nSum -= 10;
                    nTakeover = 1;
                    number.set(i, (char) ('0' + nSum));
                }
            } else {
                number.set(i, (char) ('0' + nSum));
                break;
            }
        }
        return isOverflow;
    }

    private void print(List<Character> number) {
        boolean isBegin0 = true;
        int len = number.size();
        for (int i = 0; i < len; i++) {
            if (isBegin0 && number.get(i) != '0') {
                isBegin0 = false;
            }
            if (!isBegin0) {
                System.out.print(number.get(i));
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Offer_17 solution = new Offer_17();
        solution.printNumbers(3);
    }

    // **********************************************
    /**
     * 不考虑大数的情况
     */
    public int[] printNumbers1(int n) {
        int end = (int) Math.pow(10, n) - 1;
        int[] ans = new int[end];
        for (int i = 0; i < end; i++) {
            ans[i] = i + 1;
        }
        return ans;
    }
}
